#include<bits/stdc++.h>
using namespace std;
namespace IO{
#define isDigit(x) ((x)>='0'&&(x)<='9')
template<typename T>
    inline void read(T&x){
        x=0;
        register char c=getchar();
        register bool fu=0;
        while(!isDigit(c)&&c!='-')
                c=getchar();
        if(c=='-')
            fu=1,c=getchar();
        while(isDigit(c))
            x=(x<<1)+(x<<3)+(c^48),c=getchar();
        if(fu==1)
            x=(~(x-1));
    }
    template<typename T>
    inline void _print(T x){
        if(x>9)
            _print(x/10);
        putchar((x%10)|48);
    }
    template<typename T>
    inline void print(T x){
        if(x<0)
            putchar('-'),
            _print((~(x-1)));
        else _print(x);
    }
}
using namespace IO;
int n,q;
long long tot;
const int M=1e6+5;
bitset<M>visited;
vector<bool>color;//0 -> blue ; 1 -> red
vector<int>a,lpos,rpos;
vector<pair<int,int> >score;//totscore : value
void dfs(int l,int r){
    if(l>=r)
        return;
    int x=-1;
    for(auto t:score){
        int ll=lpos[t.second],
            rr=rpos[t.second];
        if(ll>=l&&rr<=r){//found
            color[t.second]=1;
            x=t.second;
            tot+=t.first;
            break;
        }
    }
    if(x!=-1){
        dfs(l,lpos[x]-1);
        dfs(rpos[x]+1,r);
    }
}
int main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    read(q);
    while(q--){
        tot=0;
        read(n);
        visited=0;
        a=vector<int>(n+1,0);
        color=vector<bool>(M,false);
        lpos=rpos=vector<int>(M,0);
        int x,maxx=-1;
        for(int i=1;i<=n;++i){
            read(a[i]);
            maxx=max(maxx,a[i]);
        }
        score=vector<pair<int,int> >(maxx+1,{0,0});
        for(int i=1;i<=n;++i){
            x=a[i];
            score[x].second=x;
            if(!visited[x]){
                visited[x]=1;
                lpos[x]=i;
            }
            else
                score[x].first+=x;
            rpos[x]=i;
        }
        sort(score.begin(),score.end(),greater<pair<int,int> >());
        dfs(1,n);
        int pre=-1;
        for(int i=1;i<=n;++i){
            if(color[a[i]]==1)
                continue;
            if(pre==-1&&color[a[i]]==0){
                pre=i;
                continue;
            }
            if(a[i]==a[pre])
                tot+=a[i];
            pre=i;

        }
        print(tot);
        putchar('\n');
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}
